树的直径

树的直径是一个非常经典的概念,具体定义就是一颗树上的最长链。
关于直径有一个非常常见的结论:可以通过两次dfsdfs来求得树上的一条直径(直径是可以不唯一的)。首先随便选择一个点xx往外遍历找到xx能到达的最远点yy,再从yy出发往外走走到最远点zz,则yyzz的一条简单路径就是树的直径。
这个结论的证明分为两步:
dfsdfs贪心时的第二步最远点显然是正确的,一定能拿到最远距离的。
第一步是证明:从树上任意一点出发走到的最远点,一定是树上直径的一个端点。
反证法:假设某个点走出去的最远点是xxxx拓展出去得到的一个直径的候选项短于另外一组同样方式求的的AABB,那么无非就两种情况,第一种是两者不相交,如下图:

由于整个图是联通的,我们可以找到一个点TT链接两个直径,如图:

根据定义:DY,KD_{Y,K}是比DB,KD_{B,K}长的,否则不会选择yy,但是这样的话对于AA来说,选择与YY连通明显更优,与他是最长的直径矛盾了,这种情况下只有当假设正确的时候,也就是两者相等都是树上的直径的时候才是正确的。
第二个是假设他俩是相交于一点Z的话,如下
显然在交于某一点Z的时候,根据最远点的定义,一定有DA,Y>DZ.A>DZ,BD_{A,Y} > D_{Z.A} > D_{Z,B}DZ,YD_{Z,Y}是三者中最长的,但是这样的话,AA点应该选择连通向yy而不是BB,这就矛盾了,所以第二种情况也是不成立的,因为只有在假设正确的时候,也即是两者相等都是直径的时候,才不矛盾。
综上,结论是正确的,即从树上任意一点出发走到的最远点一定是直径的一个端点。
参考代码如下:
注意这个代码只是dfsdfs部分,是要跑两次的,tt就是最终的最远点。

void dfs(int u,int& t)
{
	st[u] = 1;
	for(int i = ver[u];~i;i = succ[i])
	{
		int v = edge[i];
		if(st[v] == 1)	continue;
		dist[v] = dist[u] + cost[i];
		if(dist[v] >= dist[t])	t = v;		
		dfs(v,t);
	}
	st[u] = 0;
}

但是这种贪心做法仅能应对所有权都是正权的情况,如果图里有负权,就不能用了。
在这种情况下就得用树形DP来做了,DP的具体内容就不详细展开了,说简单一点。
首先,直径如果包含xx节点,则一截是xx往他的子树下伸展得到,另一截是另一个子树伸展出去得到,形成的一条链。
定义:D[x]D[x]xx节点往以xx为根的子树下走,能走到的所有长度集合中最大的。
转移:D[x] = max{D[S] + edge(x,S)
其中SSxx的一个子节点,edge(x,S)edge(x,S)表示两点连边的权值。
其次,还得把另一边加上。
定义:F{x]是以xx为中间点形成的一条链的所有长度集合里最大的。
转移:F[x]=max(D[x]+D[S]+edge(x,S))F[x] = max(D[x] + D[S] + edge(x,S))
注意xxss是不能相同的,不然会重复计算,因此,具体代码时要先更新F[x]F[x]再更新具体的距离。
参考代码如下:
这里没有明确地写出F[]F[],直接记录并修改的最大值tt做完之后tt就是直径。

void dp(int u,int& t)
{
	st[u] = 1;
	for(int i = ver[u];~i;i = succ[i])
	{
		int v = edge[i];
		if(st[v] == 1)	continue;
		dp(v,t);
		t = max(t,dist[u] + dist[v] + cost[i]);
		dist[u] = max(dist[u],dist[v] + cost[i]);
	}
	st[u] = 0;
}